/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-10-06
 * Time:20:42
 */

/**
 * 力扣69:x的平方根
 */

public class mySqrt {

    public static void main(String[] args) {
        int x = 4;
        int n = 8;
        System.out.println(mySqrt(x));
        System.out.println(mySqrt(n));
    }

    /**
     * 二分查找
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
       int p = 0;
       int q = x;
       int end = 0;
       while (p <= q){
           int mid = p + (q - p)/2;
           if ((long)mid * mid <= x){
               end = mid;
               p = mid + 1;
           }else {
               q =mid - 1;
           }
       }
       return end;
    }
}
